//
//Copyright GX. Yuan
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @file net.go
 * @brief Leetcode practice
 * @details 搜索循转数组排序数组
 * @author GX. Yuan  any question please send mail to yuanguanxu@qq.com
 * @date 2021-6-28
 * @version V1.0
 * @attention 硬件平台: windows 10 家庭版
 * SDK版本：Go 1.16.5
 * IDE版本：GoLand 2020.2.3
 */
package main

import "fmt"

func search(nums []int, target int) int {
	var j=len(nums)-1
	var i=0
	var mid int

	// 注意边界是i<=j的处理方式
	for i<=j {
		mid=(i+j)/2
		if target ==nums[mid] {
			return mid
		}
		// 找到有序部分
		if nums[mid]>=nums[i]{ // 假设前一个部分有序的部分
			if target< nums[mid] && target>= nums[i] { // 检查是否在其中
				j=mid-1
			}else{
				i=mid+1
			}
		}else{ // 否则后一个部分是有序的部分
			if target<=nums[j] && target>nums[mid] { // 检查是否在有序部分
				i=mid+1
			}else{
				j=mid-1
			}
		}
	}
	return -1
}

func main() {
	nums := []int{3,1}
	fmt.Println(search(nums, 1))
	return
}

// 思路
// 如果直接搜索性能肯定存在问题
// 考点：旋转排序数组，查找效率
// 数组的特点是：有序的，同时没有重复，最后进行围绕一个位置进行了旋转
// 从循环的角度看，也就是，这个数组形成了一个闭环;
// 最好的方法：就是直接使用二分法进行处理；
// 这样就不需要找到旋转点了;
// 直接使用二分方法处理
//==================================
// 以上思路错误： 错误的原因是：仅仅考虑了对于中间进行旋转的情况。
//总结：旋转情况分为三个部分
// 官方的思路是：
// 二分排除法
// 将内容进行二分
// 由于内容分为两个部分，不管我如何选择中间点。那么，必然落入其中的一个点。必然存在有序的点。
// 所以我们的实现方式是，找到存在的有序的序列，进行排除；
// 最最需要考虑的是：边界问题。